\section{Background of Markov Logic}


A first-order knowledge base (KB) can be seen as a set of hard constraints
on the set of possible worlds: if a world violates even one
formula, it has zero probability. The basic idea of MLNs is to \textit{soften}
these constraints: when a world violates one formula in the KB it
is deemed \textit{less probable}, but \textit{not impossible}. The fewer formulas a
world violates, the more probable it is. Each formula has an associated
weight that reflects how strong a constraint it is: the higher
the weight, the greater the difference in log probability between a
world that satisfies the formula and one that does not, other things
being equal.

\vspace{1mm}

\noindent \textsc{Definition 1.} (From~\cite{Richardson06markovlogic})
\textit{A Markov logic network (MLN) L is a
set of pairs ($F_i$, $w_i$), where $F_i$ is a formula in first-order
logic and $w_i$ is a real number. Together with a finite set
of constants C = \{$c_1$, $c_2$, . . . , $c_{|C|}$\}, it defines a Markov
network $M_{L,C}$ as follows:}

\begin{enumerate}
\item \textit{$M_{L,C}$ contains one binary node for each possible
grounding of each predicate appearing in $L$. The value
of the node is 1 if the ground predicate is true, and 0
otherwise.}

\item \textit{$M_{L,C}$ contains one feature for each possible grounding
of each formula $F_i$ in $L$. The value of this feature
is 1 if the ground formula is true, and 0 otherwise. The
weight of the feature is the $w_i$ associated with $F_i$ in $L$.}
\end{enumerate}

Thus there is an edge between two nodes of $M_{L,C}$ iff
the corresponding ground predicates appear together in at
least one grounding of one formula in $L$. An MLN can
be viewed as a \textit{template} for constructing Markov networks.
The probability
distribution over possible worlds $x$ specified by the ground
Markov network $M_{L,C}$ is given by


\begin{equation}
P(\mathbf{X}=\mathbf{x}) = \frac{1}{Z} \prod_i \phi_i
(x_{\{i\}})
\end{equation}

where $Z$ is the normalization factor, $\phi_i$($x_{\{i\}}$)
is the potential function defined on the $ith$ clique which
is related to a grounding of formula $F_i$, and $x_{\{i\}}$
is the discrete variable vector in the clique. Usually, it
is represented as follows,

\begin{equation}
\phi_i(x_{\{i\}}) = %\frac{1}{Z} \prod_i \phi_i (x_{\{i\}})
\left\{
    \begin{array}{ll}
        e^{w_i} \quad F_i(x_{\{i\}}) = True\\
        1 \quad \quad F_i(x_{\{i\}}) = False
    \end{array}
\right.
\end{equation}

In this way, we can represent the probability as follows,

\begin{equation}
P(\mathbf{X}=\mathbf{x}) = \frac{1}{Z} \exp \left(\sum_i w_i
n_i(\mathbf{x})\right)
\end{equation}


where $n_i$($x$) is the number of true groundings of $F_i$ in $x$.



